#include<stdio.h>
#include<stdlib.h>
typedef int ElementType;

void Swap(int *a, int *b)
{
    int t = *a; *a = *b; *b = t;
}

int Selection_Sort(ElementType A[], int N)
{
    int MinPosition, cnt = 0;
    for(int i=0;i<N;i++)
    {
        MinPosition = i;
        for(int j=i+1;j<N;j++)
        {
            if(A[MinPosition] > A[j]) MinPosition = j;
            cnt++;
        }       
        Swap(&A[i], &A[MinPosition]);
    }
    return cnt;
}

int Bubble_Sort(ElementType A[], int N)
{
    int flag, cnt = 0;
    for(int P=N-1;P>=0;P--)
    {
        flag = 0;
        for(int i=0;i<P;i++) 
        {
            if (A[i] > A[i+1]) 
            {
                Swap(&A[i], &A[i+1]);
                flag = 1;
            }
            cnt++;
        }
        if(flag == 0) break;
    }
    return cnt;
}

int PercDown(ElementType A[], int p, int N)
{
    int Parent, Child, cnt = 0;
    ElementType X;
    X = A[p];
    for(Parent=p; (Parent*2+1)<N; Parent=Child) {
        Child = Parent * 2 + 1;
        if(Child != N-1 && A[Child] < A[Child+1])
            Child++;
        cnt++;
        if(X >= A[Child]) break;
        else
            A[Parent] = A[Child];
    }
    A[Parent] = X;
    return cnt;
}

int Heap_Sort(ElementType A[], int N)
{
    int i, cnt = 0;
    for(i=N/2-1; i>=0; i--)
        cnt += PercDown(A, i, N);    
    for(i=N-1;i>0;i--) {
        Swap(&A[0], &A[i]);
        cnt += PercDown(A, 0, i);
    }
    return cnt;
}

int Merge(ElementType A[], ElementType TmpA[], int L, int R, int RightEnd)
{
    int LeftEnd, NumElements, Tmp;
    int i, cnt = 0;   
    LeftEnd = R - 1;
    Tmp = L;
    NumElements = RightEnd - L + 1;
    while (L <= LeftEnd && R <= RightEnd)
    {
        cnt++;
        if (A[L] <= A[R])
            TmpA[Tmp++] = A[L++];
        else
            TmpA[Tmp++] = A[R++];
    }
    while (L <= LeftEnd)
        TmpA[Tmp++] = A[L++];
    while (R <= RightEnd)
        TmpA[Tmp++] = A[R++];

    for(i = 0;i < NumElements;i++,RightEnd--)
        A[RightEnd] = TmpA[RightEnd];
    return cnt;
}

int Msort(ElementType A[], ElementType TmpA[], int L, int RightEnd)
{ 
    int Center, cnt = 0;    
    if (L < RightEnd) {
        Center = (L+RightEnd) / 2;
        cnt += Msort(A, TmpA, L, Center);
        cnt += Msort(A, TmpA, Center + 1, RightEnd);
        cnt += Merge(A, TmpA, L, Center + 1, RightEnd);
    }
    return cnt;
}

int Merge_Sort(ElementType A[], int N)
{
    int cnt;
    ElementType *TmpA;
    TmpA = (ElementType *)malloc(N*sizeof(ElementType));   
    cnt = Msort(A, TmpA, 0, N-1);
    free(TmpA);
    return cnt;
}

int quickSort(int k[], int left, int right)
{     
    int i, last, cnt = 0;
    if(left < right)
    {
        last = left; 
        for(i=left+1;i<=right;i++)
        {
            cnt++;
            if(k[i] < k[left]) Swap(&k[++last], &k[i]);                
        }
        Swap(&k[left], &k[last]);
        cnt += quickSort(k, left, last-1); 
        cnt += quickSort(k, last+1, right);   
    }
    return cnt;
}

int Quick_Sort(ElementType A[], int N)
{
    int cnt = quickSort(A, 0, N-1);
    return cnt;
}

int main()
{
    int n, op, cnt = 0;
    scanf("%d%d", &n, &op);
    int a[n];
    for(int i=0;i<n;i++) scanf("%d", &a[i]);
    switch (op)
    {
        case 1:
            cnt = Selection_Sort(a, n);
            break;
        case 2:
            cnt = Bubble_Sort(a, n);
            break;
        case 3:
            cnt = Heap_Sort(a, n);
            break;
        case 4:
            cnt = Merge_Sort(a, n);
            break;
        case 5:
            cnt = Quick_Sort(a, n);
            break;
        default:
            break;
    }
    for(int i=0;i<n;i++) printf("%d ", a[i]);
    printf("\n%d", cnt);
    return 0;
}